package 剑指offer;

public class Offer13_JZ66_02 {
    public static int movingCount(int threshold, int rows, int cols) {
        if (threshold<0 || rows<=0 || cols<=0) return 0;
        int[] visited = new int[rows*cols];
        int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
        return count;
    }

    public static int movingCountCore(int threshold, int rows, int cols, int row, int col, int[] visited) {
        int count = 0;
        if (check(threshold, rows, cols, row, col, visited)) {
            visited[row*cols+col] = 1;
            count = 1 + movingCountCore(threshold, rows, cols, row-1, col, visited)
                    + movingCountCore(threshold, rows, cols, row+1, col, visited)
                    + movingCountCore(threshold, rows, cols, row, col-1, visited)
                    + movingCountCore(threshold, rows, cols, row, col+1, visited);
        }
        return count;
    }

    public static boolean check(int threshold, int rows, int cols, int row, int col, int[] visited) {
        if (row>=0 && row<rows && col>=0 && col<cols && visited[row*cols+col]==0 && (getDigital(row)+getDigital(col))<=threshold) {
            return true;
        }
        return false;
    }

    public static int getDigital(int num) {
        int sum = 0;
        while (num%10 != 0) {
            sum += num%10;
            num = num/10;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(movingCount(5, 10, 10));
    }
}
